package leetcode_core.sort;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年01月03日 23:11
 */
public class QuickSort {
    private void quickSort(int[] arr,int L,int R){
        if(L<R){
            swap(arr,L+(int)(Math.random()*(R-L+1)),R);
            int[] partition = partition(arr, L, R);
            quickSort(arr,L,partition[0]-1);
            quickSort(arr,partition[1]+1,R);
        }
    }
    private int[] partition(int[] arr,int L,int R){
        int less = L-1;//<区的左边界
        int more = R;//>区的右边界
        while (L<more){
            if(arr[L]<arr[R]){//当前这个数小于划分值
                swap(arr,++less,L++);
            }else if(arr[L]>arr[R]){
                swap(arr,--more,L);
            }else{
                L++;
            }
        }
        swap(arr,more,R);
        return new int[]{less+1,more};
    }
    private void swap(int[] arr,int i,int j){
        arr[i] = arr[i]^arr[j];
        arr[j] = arr[i]^arr[j];
        arr[i] = arr[i]^arr[j];
    }
}
